/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package open.algo.sort;

/**
 *
 * @SortAnnoation(averageTime="o(n2)", worstTime="o(n2)", space = "o(1)", stable = true, feature= "nearly no use, very simple to implement")
 *
 * @author fli
 */
public class BubbleSort implements Sort
{

    @Override
    public void sort(int[] a)
    {
        bsort_2(a);
    }

    /**
     * bubble up
     *
     * @param a
     */
    public void bsort(int[] a)
    {
        boolean s = true;
        for (int i = 0; i < a.length && s; i++)
        {
            s = false;
            for (int j = a.length - 1; j > i; j--)
            {
                if (a[j - 1] > a[j])
                {
                    Swap.swap(a, j - 1, j);
                    s = true;
                }
            }
        }
    }

    /**
     * bubble down
     * 
     * @param a
     */
    public void bsort_2(int[] a)
    {
        int n = a.length;
        boolean s = true;
        do
        {
            s = false;
            for (int i = 0; i < n - 1; i++)
            {
                if (a[i] > a[i + 1])
                {
                    Swap.swap(a, i + 1, i);
                    s = true;
                }
            }

            n--;
        } while (s);
    }

    @Override
    public String toString()
    {
        return "bubblesort";
    }
}
